package com.ajin.hot100;

import java.util.HashMap;
import java.util.HashSet;

public class Code8 {
    public static void main(String[] args) {
        String s = "abcabcbb";
        int length = lengthOfLongestSubstring(s);
        System.out.println(length);
    }
    /**
     * 无重复字符最长子串
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
     * 示例 1:
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 示例 2:
     * 输入: s = "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * 示例 3:
     * 输入: s = "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        int max = 0;
        //定义一个变量，如果遇到重复则更新到重复的索引+1，到时候遍历
        int left = 0;
        //2.利用hashMap和指针
        HashMap<Character, Integer> map = new HashMap<>();
        for (int right = 0; right < s.length(); right++) {
            //加入map，字符串为key，值为索引值
            char c = s.charAt(right);
            //如果已经包含这个key，代表这个字串重复出现，则更新left位置
            if(map.containsKey(c)){
                left = Math.max(left,map.get(c)+1);
            }
            map.put(c,right);
            //更新max值
            max = Math.max(max,right-left+1);

        }
        return max;
    }
    public int lengthOfLongestSubstring1(String s) {
        int maxLen = 0;
        int left = 0, right = 0;
        HashSet<Character> set = new HashSet<>();
        while (right < s.length()) {
            char c = s.charAt(right);
            // 如果窗口中已存在当前字符，就从左侧移除，直到不再重复
            if (set.contains(c)) {
                // 移除 s[left]，并左移窗口
                set.remove(s.charAt(left));
                left++;
            } else {
                // 不重复则加入窗口，更新最大长度，并右移
                set.add(c);
                right++;
                maxLen = Math.max(maxLen, right - left);
                // 注意：这里也可写成 right-left+1，但是由于 right 已经先 ++ 了，所以只需 right-left
            }
        }
        return maxLen;
    }

    public int lengthOfLongestSubstring2(String s) {
        //1.利用set集合来判断字符是否重复
        int max = 0;
        //2.暴力解法，需要两层for
        for (int i = 0; i < s.length(); i++) {
            HashSet<Character> set = new HashSet<>();
            for (int j = i; j < s.length(); j++) {
                char c = s.charAt(j);
                if (set.contains(c)) {
                    break;
                }
        //3.如果set存在则break内循环
        //4.更新最大长度
                set.add(c);
                max = Math.max(max, j - i + 1);
            }
        }
        return max;
    }
}
